{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Depth of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDepth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的最小深度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树，找出其最小深度。</p>\n",
    "\n",
    "<p>最小深度是从根节点到最近叶子节点的最短路径上的节点数量。</p>\n",
    "\n",
    "<p><strong>说明：</strong>叶子节点是指没有子节点的节点。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg\" style=\"width: 432px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [2,null,3,null,4,null,5,null,6]\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数的范围在 <code>[0, 10<sup>5</sup>]</code> 内</li>\n",
    "\t<li><code>-1000 <= Node.val <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-depth-of-binary-tree](https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-depth-of-binary-tree](https://leetcode.cn/problems/minimum-depth-of-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[2,null,3,null,4,null,5,null,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        depth = 1\n",
    "\n",
    "        while not len(q) == 0:\n",
    "            size = len(q)\n",
    "\n",
    "            for i in range(size):\n",
    "                cur = q.popleft()\n",
    "                if not cur.left and not cur.right:\n",
    "                    return depth\n",
    "                if cur.left:\n",
    "                    q.append(cur.left)\n",
    "                if cur.right:\n",
    "                    q.append(cur.right)\n",
    "            depth += 1\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: 'TreeNode') -> 'int':\n",
    "        queue = []\n",
    "        if root:\n",
    "            queue.append((root, 0))\n",
    "        while queue:\n",
    "            node, depth = queue.pop(0)\n",
    "            if not node.left and not node.right:\n",
    "                return depth + 1\n",
    "            if node.left:\n",
    "                queue.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, depth + 1))\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: 'TreeNode') -> 'int':\n",
    "        if not root:\n",
    "            return 0\n",
    "        n = 1\n",
    "        q = [root, ]\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            for i in range(size):\n",
    "                current = q.pop(0)\n",
    "                if not current.left and not current.right:\n",
    "                    return n\n",
    "                if current.left:\n",
    "                    q.append(current.left)\n",
    "                if current.right:\n",
    "                    q.append(current.right)\n",
    "            n += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            if root.left and not root.right:\n",
    "                return self.minDepth(root.left)+1\n",
    "            elif root.right and not root.left:\n",
    "                return self.minDepth(root.right)+1\n",
    "            elif root.left and root.right:\n",
    "                return min(self.minDepth(root.left), self.minDepth(root.right))+1\n",
    "            else:\n",
    "                return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        children = [root.left,root.right]\n",
    "        \n",
    "        if not any(children):\n",
    "            return 1\n",
    "            \n",
    "        \n",
    "        min_depth = float('inf')\n",
    "        for c in children:\n",
    "            if c:\n",
    "                min_depth = min(self.minDepth(c),min_depth)\n",
    "                \n",
    "        return min_depth+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        # BFS: 查找第一个左右孩子都为空的节点的深度\n",
    "        # 1. 创建队列\n",
    "        if not root: return 0\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = 0\n",
    "        while queue:\n",
    "            res = res + 1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left != None: queue.append(node.left)\n",
    "                if node.right != None: queue.append(node.right)\n",
    "                if node.right == None and node.left == None:\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        '''\n",
    "        if root is None:\n",
    "            return 0\n",
    "        queue = [root]\n",
    "        depth = 1\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right:queue.append(node.right)\n",
    "                if node.left is None and node.right is None:\n",
    "                    return depth\n",
    "                depth += 1'''\n",
    "        if not root: return 0\n",
    "        queue = [root]\n",
    "        depth = 1\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                cur = queue.pop(0)\n",
    "                if cur.left: queue.append(cur.left)\n",
    "                if cur.right: queue.append(cur.right)\n",
    "                if cur.left is None and cur.right is None: return depth\n",
    "            depth += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        q = [root]\n",
    "        minDepth, iLeft, iRight = 1, -1, -1\n",
    "        midNodeList = []\n",
    "        while len(q) != 0:\n",
    "            node = q.pop(0)\n",
    "            if node.left:\n",
    "                midNodeList.append(node.left)\n",
    "            if node.right:\n",
    "                midNodeList.append(node.right)\n",
    "            if not node.left and not node.right:\n",
    "                return minDepth\n",
    "            if len(q) == 0 and len(midNodeList) != 0:\n",
    "                minDepth += 1\n",
    "                for iNode in midNodeList:\n",
    "                    q.append(iNode)\n",
    "                midNodeList.clear()\n",
    "\n",
    "        return minDepth\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        if not root.left and not root.right:\n",
    "            res = 1\n",
    "        elif root.left and root.right:\n",
    "            res = 1 + min(self.minDepth(root.left), self.minDepth(root.right))\n",
    "        elif root.left and not root.right:\n",
    "            res = 1 + self.minDepth(root.left)\n",
    "        else:\n",
    "            res = 1 + self.minDepth(root.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        set1=set()\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(root,count):\n",
    "            if not root:\n",
    "                return\n",
    "            count+=1\n",
    "            if not root.left and not root.right:\n",
    "                set1.add(count)\n",
    "                return \n",
    "            l=dfs(root.left,count)\n",
    "            r=dfs(root.right,count)\n",
    "        dfs(root,0)\n",
    "        return min(set1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        ## bfs\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 1\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                cur = queue[0]\n",
    "                del queue[0]\n",
    "                if cur.left is None and cur.right is None:\n",
    "                    return depth\n",
    "                else:\n",
    "                    if cur.left:\n",
    "                        queue.append(cur.left)\n",
    "                    if cur.right:\n",
    "                        queue.append(cur.right)\n",
    "            depth += 1\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if root is None:\n",
    "        #     return 0\n",
    "        # min_left = self.minDepth(root.left) if root.left is not None else 0\n",
    "        # min_right = self.minDepth(root.right) if root.right is not None else 0\n",
    "        # return min(min_left, min_right) + 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.left and root.right:\n",
    "            depth1 = self.minDepth(root.left)\n",
    "            depth2 = self.minDepth(root.right)\n",
    "            return min(depth1, depth2) + 1\n",
    "        elif root.left:\n",
    "            return self.minDepth(root.left) + 1\n",
    "        else:\n",
    "            return self.minDepth(root.right) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 1\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            lenth = len(queue)\n",
    "            for _ in range(lenth):\n",
    "                node = queue.popleft()\n",
    "                if not node: continue\n",
    "                if not node.left and not node.right:\n",
    "                    return res \n",
    "                queue.append(node.left)\n",
    "                queue.append(node.right)\n",
    "            res += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = float('inf')\n",
    "        def dfs(root, depth):\n",
    "            if depth >= self.res:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                self.res = min(self.res, depth)\n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left, depth+1)\n",
    "            if root.right:\n",
    "                dfs(root.right, depth+1)\n",
    "        dfs(root, 1)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        def _minDepth(root):\n",
    "            if root.left is None and root.right is None:\n",
    "                return 1\n",
    "            \n",
    "            if root.left and root.right is None:\n",
    "                left = self.minDepth(root.left)\n",
    "                return left + 1\n",
    "            elif root.right and root.left is None:\n",
    "                right = self.minDepth(root.right)\n",
    "                return right + 1\n",
    "            else:\n",
    "                left = self.minDepth(root.left)\n",
    "                right = self.minDepth(root.right)\n",
    "                return min(left, right) + 1\n",
    "            \n",
    "        return _minDepth(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        if not root.left and not root.right: \t# 叶子节点\n",
    "            ans = 1\n",
    "        elif root.left and root.right:  # 左右子树均不为空\n",
    "            ans = min(self.minDepth(root.left), self.minDepth(root.right)) + 1\n",
    "        elif root.left:\t\t# 左子树不为空 & 右子树为空\n",
    "            ans = self.minDepth(root.left) + 1\n",
    "        else:\t\t\t# 左子树为空 & 右子树不为空\n",
    "            ans = self.minDepth(root.right) + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        if not root.left and not root.right:\n",
    "            ans = 1\n",
    "        elif root.left and root.right:\n",
    "            ans = min (self.minDepth(root.left), self.minDepth(root.right))+1\n",
    "        elif root.left:\n",
    "            ans = self.minDepth(root.left)+1\n",
    "        else:\n",
    "            ans = self.minDepth(root.right)+1\n",
    "        return ans\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def minDepth(self, root: TreeNode) -> int:\n",
    "#         if not root:\n",
    "#            return 0\n",
    "        \n",
    "#         from collections import deque\n",
    "#         q = deque()\n",
    "#         q.append(root)\n",
    "#         depth = 1\n",
    "\n",
    "#         while q:\n",
    "#             size = len(q)\n",
    "#             for _ in range(size):\n",
    "#                 node = q.popleft()\n",
    "#                 if not node.left and not node.right:\n",
    "#                     return depth\n",
    "#                 if node.left:\n",
    "#                     q.append(node.left)\n",
    "#                 if node.right:\n",
    "#                     q.append(node.right)\n",
    "#             depth += 1\n",
    "#         return depth\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 1\n",
    "        \n",
    "        depth = 1\n",
    "\n",
    "        if not root.left:\n",
    "            depth += self.minDepth(root.right)\n",
    "        elif not root.right:\n",
    "            depth += self.minDepth(root.left)\n",
    "        else:\n",
    "            left_depth = self.minDepth(root.left)\n",
    "            right_depth = self.minDepth(root.right)\n",
    "            depth += min(left_depth, right_depth)\n",
    "        \n",
    "        return depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        children = [root.left, root.right]\n",
    "        if not any(children):\n",
    "            return 1\n",
    "        min_depth = float('inf')\n",
    "        for c in children:\n",
    "            if c:\n",
    "                min_depth = min(self.minDepth(c), min_depth)\n",
    "        return min_depth + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = 0\n",
    "\n",
    "        def dfs(root, depth):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.left and not root.right:\n",
    "                self.res = min(self.res, depth) if self.res else depth\n",
    "                return\n",
    "            dfs(root.left, depth+1)\n",
    "            dfs(root.right, depth+1)\n",
    "\n",
    "        dfs(root, 1)\n",
    "        return self.res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        def dfs(root,min_deep):\n",
    "            if not root:\n",
    "                return min_deep\n",
    "            elif root.left and root.right:\n",
    "                return min(dfs(root.left,min_deep+1),dfs(root.right,min_deep+1))\n",
    "            elif root.left:\n",
    "                return dfs(root.left,min_deep+1)\n",
    "            else:\n",
    "                return dfs(root.right,min_deep+1)\n",
    "        x=dfs(root,0)\n",
    "        return x\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        self.min_d = float('inf')\n",
    "        if not root:return 0\n",
    "        #dfs\n",
    "        def helper(node,tmp):\n",
    "            if not node.left and not node.right:\n",
    "                self.min_d = min(self.min_d,len(tmp))\n",
    "            if node.left:\n",
    "                helper(node.left,tmp + [node.left.val])\n",
    "            if node.right:\n",
    "                helper(node.right,tmp + [node.right.val])\n",
    "        helper(root,[root.val])\n",
    "        return self.min_d\n",
    "        #bfs\n",
    "        from collections import deque\n",
    "        queue = deque()\n",
    "        queue.append([root,[root.val]])\n",
    "        while queue:\n",
    "            node,tmp = queue.pop()\n",
    "            if not node.left and not node.right:\n",
    "                self.min_d = min(self.min_d,len(tmp))\n",
    "            if node.left:\n",
    "                queue.appendleft([node.left,tmp + [node.left.val]])\n",
    "            if node.right:\n",
    "                queue.appendleft([node.right,tmp + [node.right.val]])\n",
    "        return self.min_d\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        level,que=0,[root]\n",
    "        while que:\n",
    "            level+=1\n",
    "            x=[]\n",
    "            for q in que:\n",
    "                if q.left :\n",
    "                    x.append(q.left)\n",
    "                if q.right:\n",
    "                    x.append(q.right)\n",
    "                if not q.left and not q.right:\n",
    "                    return level\n",
    "            que=x\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        self.min_depth = float(\"inf\")\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        def helper(root, path):\n",
    "            # print([i.val for i in path])\n",
    "            path.append(root)\n",
    "            if root.left==None and root.right==None:\n",
    "                self.min_depth = min(self.min_depth, len(path))\n",
    "\n",
    "            if root.left:\n",
    "                helper(root.left, path[:])\n",
    "            if root.right:\n",
    "                helper(root.right, path[:])\n",
    "\n",
    "        helper(root, [])\n",
    "        return self.min_depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        import numpy as np\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        def find(node: TreeNode, depth: int):\n",
    "            d_left = np.inf\n",
    "            d_right = np.inf\n",
    "            if not (node.left or node.right):\n",
    "                return depth\n",
    "            if node.left:\n",
    "                d_left = find(node.left, depth + 1)\n",
    "            if node.right:\n",
    "                d_right = find(node.right, depth + 1)\n",
    "            return min(d_left, d_right)\n",
    "\n",
    "        return find(root, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def DFS(root,d):\n",
    "    if not root:\n",
    "        return\n",
    "    left = root.left\n",
    "    right = root.right\n",
    "    d[left] = d[root]+1\n",
    "    d[right] = d[root]+1\n",
    "    DFS(left,d)\n",
    "    DFS(right,d)\n",
    "    \n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minDepth(self, root):\n",
    "        if not root:return 0\n",
    "        d = {}\n",
    "        d[root] = 1\n",
    "        # return re\n",
    "        DFS(root,d)\n",
    "        minv = np.inf\n",
    "\n",
    "        for x in d.keys():\n",
    "            if x and not x.left and not x.right:\n",
    "                if d[x] < minv:\n",
    "                    minv = d[x]\n",
    "        return minv\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        seen = dict()\n",
    "        def dg(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            HR = 0\n",
    "            HL = 0\n",
    "            H = 0\n",
    "            if root:\n",
    "                if root.right in seen:\n",
    "                    HR = seen[root.right]\n",
    "                else:\n",
    "                    HR = dg(root.right)\n",
    "                    seen[root.right] = HR\n",
    "                if root.left in seen:\n",
    "                    HL = seen[root.left]\n",
    "                else:\n",
    "                    HL = dg(root.left)\n",
    "                    seen[root.left] = HL\n",
    "\n",
    "                if HR!=0 and HL!=0:\n",
    "                    H = min(HR,HL)+1\n",
    "                if HR==0 or HL==0:\n",
    "                    H = max(HR,HL)+1    \n",
    "\n",
    "            return H\n",
    "        \n",
    "        return dg(root)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        if root.left == None and root.right == None:     # 左右都空，是叶子节点\n",
    "            return 1\n",
    "        if root.left != None and root.right == None:     # 左非空\n",
    "            return 1 + self.minDepth(root.left)\n",
    "        if root.right != None and root.left == None:     # 右非空\n",
    "            return 1 + self.minDepth(root.right)\n",
    "        return np.min([1 + self.minDepth(root.left), 1 + self.minDepth(root.right)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        if root.left and not root.right:\n",
    "            return self.minDepth(root.left)+1\n",
    "        if not root.left and root.right:\n",
    "            return self.minDepth(root.right)+1\n",
    "        root.left=self.minDepth(root.left)\n",
    "        root.right=self.minDepth(root.right)\n",
    "        return min(root.left,root.right)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        # BFS有个特点挺适合最小深度\n",
    "        # 就是它像是层次遍历，每次要扫完一层\n",
    "        # 这个过程中遇到一个没孩子的就确定这层是最小层数，就不用继续遍历了\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        cur_level = 0\n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            cur_level += 1\n",
    "            for _ in range(level_size):\n",
    "                node = queue.popleft() # 一定要从队尾开始pop\n",
    "                if not node.left and not node.right:\n",
    "                    return cur_level\n",
    "                if node.left: queue.append(node.left) \n",
    "                # 这里逻辑在重写第一遍的时候写错了，写成if not node.left了\n",
    "                if node.right: queue.append(node.right)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        # 广度优先  层次遍历 使用栈\n",
    "        if not root:\n",
    "            return 0\n",
    "        # 将根节点和深度入栈\n",
    "        que = collections.deque([(root, 1)])\n",
    "        # 找到一个子节点时终止循环\n",
    "        while que:\n",
    "            tmp, depth = que.popleft()\n",
    "            # 找到第一个子节点时终止\n",
    "            if not tmp.left and not tmp.right:\n",
    "                return depth\n",
    "            if tmp.left:\n",
    "                que.append((tmp.left, depth+1))\n",
    "            if tmp.right:\n",
    "                que.append((tmp.right, depth+1))\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "\n",
    "        if root is None:\n",
    "            return 0;\n",
    "        Q = [root];\n",
    "        depth = 1;\n",
    "        while Q:\n",
    "            # node = Q.pop();\n",
    "            for i in range(len(Q)):\n",
    "                node = Q.pop(0);\n",
    "                if not node.left and not node.right:\n",
    "                    return depth\n",
    "                if node.left:\n",
    "                    Q.append(node.left);\n",
    "                if node.right:\n",
    "                    Q.append(node.right);\n",
    "            depth+=1;\n",
    "\n",
    "        return depth;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        # if root is None:\n",
    "        #     return 0\n",
    "        # if not root.left and not root.right:\n",
    "        #     return 1\n",
    "        # mindepth = 10**9\n",
    "        # if root.left:\n",
    "        #     mindepth = min(self.minDepth(root.left),mindepth)\n",
    "        # if root.right:\n",
    "        #     mindepth = min(self.minDepth(root.right),mindepth)\n",
    "        # return mindepth+1\n",
    "        if not root:\n",
    "            return 0\n",
    "        que = collections.deque([(root,1)])\n",
    "        while que:\n",
    "            node, depth = que.popleft()\n",
    "            if not node.left and not node.right:\n",
    "                return depth\n",
    "            if node.left:\n",
    "                que.append([node.left,depth+1])\n",
    "            if node.right:\n",
    "                que.append([node.right,depth+1])\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:return 0\n",
    "        # bfs,第一次遍历到叶子节点\n",
    "        queue=collections.deque()\n",
    "        queue.append(root)\n",
    "        depth=1\n",
    "        while queue:\n",
    "            size=len(queue)\n",
    "            for _ in range(size):\n",
    "                node=queue.popleft()\n",
    "                if node.left is None and node. right is None:return depth\n",
    "                if node.left:queue.append(node.left)\n",
    "                if node.right:queue.append(node.right)\n",
    "            depth+=1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:return 0\n",
    "        from collections import deque\n",
    "        que=deque()\n",
    "        que.append(root)\n",
    "        count=0\n",
    "        while que:\n",
    "            size=len(que)\n",
    "            count+=1\n",
    "            for _ in range(size):\n",
    "                cur=que.popleft()\n",
    "                if not cur.left and not cur.right: return count\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                     que.append(cur.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            for i in range(len(stack)):\n",
    "                x = stack[0]\n",
    "                stack = stack[1:]\n",
    "                if not x.left and not x. right:\n",
    "                    stack = []\n",
    "                    break\n",
    "                if x.left:\n",
    "                    stack.append(x.left)\n",
    "                if x.right:\n",
    "                    stack.append(x.right)\n",
    "            depth+=1\n",
    "        return depth\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        que = deque([])\n",
    "        res = 1\n",
    "        min = float(\"inf\")\n",
    "\n",
    "        if root == None:\n",
    "            return 0\n",
    "        \n",
    "        que.append(root)\n",
    "        while que:\n",
    "            size = len(que)\n",
    "\n",
    "            for i in range(size):\n",
    "                node = que[0]\n",
    "                que.popleft()\n",
    "\n",
    "                if not node.left and not node.right:\n",
    "                    min = min if min < res else res\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right:\n",
    "                    que.append(node.right)\n",
    "            res += 1\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "from unittest import result\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\r\n",
    "        if root is None:\r\n",
    "            return 0\r\n",
    "        \r\n",
    "        depth = 0\r\n",
    "\r\n",
    "        from collections import deque\r\n",
    "\r\n",
    "        que = deque([root])\r\n",
    "        while que:\r\n",
    "            size = len(que)\r\n",
    "            depth += 1\r\n",
    "            for _ in range(size):\r\n",
    "                node = que.popleft()\r\n",
    "                if node.left:\r\n",
    "                    que.append(node.left)\r\n",
    "                if node.right:\r\n",
    "                    que.append(node.right)\r\n",
    "                if node.left is None and node.right is None:\r\n",
    "                    return depth\r\n",
    "        \r\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "#         depth = 0\n",
    "#         if root == None:\n",
    "#             return depth\n",
    "#         from collections import deque\n",
    "#         queue = deque([root])\n",
    "#         while queue:\n",
    "#             size = len(queue)\n",
    "#             depth+=1\n",
    "#             for i in range(size):                \n",
    "#                 cur = queue.popleft()\n",
    "#                 if cur.left == None and cur.right==None:\n",
    "#                     return depth\n",
    "#                 if cur.left:\n",
    "#                     queue.append(cur.left)\n",
    "#                 if cur.right:\n",
    "#                     queue.append(cur.right)\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        queue = [(root,1)]\n",
    "        while queue:\n",
    "            cur, depth = queue.pop(0)\n",
    "            if cur.left==None and cur.right==None:\n",
    "                return depth\n",
    "            if cur.left:\n",
    "                queue.append((cur.left,depth+1))\n",
    "            if cur.right:\n",
    "                queue.append((cur.right,depth+1))\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        queue = collections.deque([root])\n",
    "        depth = 0\n",
    "        while queue:\n",
    "            depth += 1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "\n",
    "                if not node.left and not node.right:\n",
    "                    return depth\n",
    "                \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "        return depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        que=collections.deque([root])\n",
    "        min_depth=0\n",
    "        while que:\n",
    "            min_depth+=1\n",
    "            for _ in range(len(que)):\n",
    "                cur=que.popleft()\n",
    "                if not cur.left and not cur.right:\n",
    "                    return min_depth\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:  # 空树\n",
    "            return 0\n",
    "        que = [None] * 100000\n",
    "        l, r = 0, 0\n",
    "        que[r] = root\n",
    "        r += 1\n",
    "        level = 1\n",
    "        while l < r:\n",
    "            size = r - l\n",
    "            for i in range(size):\n",
    "                cur = que[l]\n",
    "                l += 1\n",
    "                if cur.left is not None:\n",
    "                    que[r] = cur.left\n",
    "                    r += 1\n",
    "                if cur.right is not None:\n",
    "                    que[r] = cur.right\n",
    "                    r += 1\n",
    "                if cur.left is None and cur.right is None:\n",
    "                    return level\n",
    "            level += 1\n",
    "        return level\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        queue = collections.deque([root])\n",
    "        layer = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            layer += 1\n",
    "            while size:\n",
    "                size -= 1\n",
    "                node = queue.popleft()\n",
    "                if not node.left and not node.right:\n",
    "                    return layer\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack=collections.deque([root])\n",
    "        #min_length=0\n",
    "        min_height=0\n",
    "        while stack:\n",
    "            for _ in range(len(stack)):\n",
    "                r=stack.popleft()\n",
    "                if not r.left and not r.right:\n",
    "                    return min_height+1\n",
    "                if r.left:\n",
    "                    stack.append(r.left)\n",
    "                if r.right:\n",
    "                    stack.append(r.right)\n",
    "            min_height+=1\n",
    "        '''while queue:\n",
    "            n=len(queue)\n",
    "            for n in range(n):\n",
    "                root=queue.popleft()\n",
    "                if root.left==None and root.right==None:\n",
    "                    min_length+=1\n",
    "                    return min_length\n",
    "                if root.left:\n",
    "                    queue.append(root.left)\n",
    "                if root.right:\n",
    "                    queue.append(root.right)\n",
    "            min_length+=1'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        depth = 100010\n",
    "        def dfs(node, cur_depth):\n",
    "            nonlocal depth\n",
    "            if not node or cur_depth >= depth : return\n",
    "            if (not node.left) and (not node.right):\n",
    "                # 判断是叶子节点\n",
    "                depth = min(depth, cur_depth)\n",
    "            dfs(node.left, cur_depth+1)\n",
    "            dfs(node.right, cur_depth+1)\n",
    "        \n",
    "        dfs(root, 1)\n",
    "        return depth\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root.left is not None and root.right is None:\n",
    "            return self.minDepth(root.left) + 1\n",
    "        if root.right is not None and root.left is None:\n",
    "            return self.minDepth(root.right) + 1\n",
    "        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            if not root.left:\n",
    "                return self.minDepth(root.right)+1\n",
    "            if not root.right:\n",
    "                return self.minDepth(root.left)  +1 \n",
    "            return min(self.minDepth(root.left),self.minDepth(root.right)) +1\n",
    "        \n",
    "\n",
    "        \n",
    "        c = 0\n",
    "        while root.left or root.right:\n",
    "            checknode(root.left,c)\n",
    "            checknode(root.right,c)\n",
    "\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        leftheight = self.minDepth(root.left)\n",
    "        rightheight = self.minDepth(root.right)\n",
    "        if not root.left and root.right: return 1 + rightheight\n",
    "        if not root.right and root.left: return 1 + leftheight\n",
    "        return 1 + min(leftheight, rightheight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        depth = []  # 用于存储叶子节点的深度的列表\n",
    "        if not root: return 0  # 如果根节点为空，返回深度为0\n",
    "\n",
    "        def dfs(node, d):\n",
    "            if not node.left and not node.right:  # 判断当前节点是否为叶子节点\n",
    "                depth.append(d)  # 将叶子节点的深度添加到列表中\n",
    "                return\n",
    "            d += 1  # 深度加1\n",
    "            if node.left:\n",
    "                dfs(node.left, d)  # 递归遍历左子节点\n",
    "            if node.right:\n",
    "                dfs(node.right, d)  # 递归遍历右子节点\n",
    "\n",
    "        dfs(root, 1)  # 调用递归函数，开始遍历二叉树\n",
    "        return min(depth)  # 返回叶子节点的最小深度"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "        # 如果树为空，则函数返回0\n",
    "        if not root:\n",
    "            return 0\n",
    "        # 如果树没有左子树和右子树，则函数返回1\n",
    "        if not root.left and not root.right:\n",
    "            return 1\n",
    "        # 变量min_depth值为10的9次方\n",
    "        min_depth = 10**9\n",
    "        # 如果 root 的左子节点存在，则对左子节点递归调用 minDepth 函数，并相应地更新最小深度\n",
    "        if root.left:\n",
    "            min_depth = min(self.minDepth(root.left), min_depth)\n",
    "        # 如果 root 的右子节点存在，则对右子节点递归调用 minDepth 函数，并相应地更新最小深度\n",
    "        if root.right:\n",
    "            min_depth = min(self.minDepth(root.right), min_depth)\n",
    "        # 最终结果是迄今为止找到的最小深度，加上 1\n",
    "        return min_depth + 1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
